package com.demo.java.OD201_250.OD235;

import java.util.*;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【预订酒店】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/145933384
 */
public class OdMain {
    public static void main(String[] args) {
        // 创建扫描器对象获取输入
        Scanner scanner = new Scanner(System.in);

        // 读取输入的参数 n (酒店数量), k (选择数量), x (目标价格)
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        int x = scanner.nextInt();

        // 创建一个数组来存储酒店价格
        int[] prices = new int[n];
        for (int i = 0; i < n; i++) {
            prices[i] = scanner.nextInt(); // 读取每个酒店的价格
        }

        // 获取 k 个最接近目标价格的酒店价格
        PriorityQueue<Integer> heap = findBestPrices(prices, k, x);

        // 存储选出的 k 个最接近的价格
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            res.add(heap.poll());  // 从堆中弹出最小元素
        }

        // 对结果进行排序，确保输出顺序是升序的
        Collections.sort(res);

        // 输出最终结果
        System.out.println(res.toString().replaceAll("[\\[\\],]", ""));  // 去除 List 默认的中括号和逗号
    }

    // 根据价格与目标值的距离构建一个优先队列（最小堆）
    private static PriorityQueue<Integer> findBestPrices(int[] prices, int k, int x) {
        // 创建一个优先队列，优先按价格与目标价格的差值排序
        PriorityQueue<Integer> heap = new PriorityQueue<>((o1, o2) -> {
            int diff1 = Math.abs(o1 - x);  // 计算 o1 与目标值的差
            int diff2 = Math.abs(o2 - x);  // 计算 o2 与目标值的差
            // 如果差值相等，比较价格本身
            return diff1 == diff2 ? Integer.compare(o1, o2) : Integer.compare(diff1, diff2);
        });

        // 将每个价格加入堆
        for (int price : prices) {
            heap.add(price);
        }

        return heap;
    }
}